-
Notifications
You must be signed in to change notification settings - Fork 0
/
regex for dividing by sqrt2, with variable-length lookbehind.txt
166 lines (159 loc) · 7.24 KB
/
regex for dividing by sqrt2, with variable-length lookbehind.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
# Given an input number N in the domain ^x*$, this regex returns floor(N / sqrt(2))
(?=
(x(x*)) # \1 = will be the square root of the main number, rounded down; \2 = \1 - 1
.*(?=\1*$)
\2+$
)
# Step 1: Calculate N*N in base floor(sqrt(N))+1. Thanks to this choice of number base to work in, we'll be able to use the
# second shortened form of division in all places where the number base is the divisor, because it's guaranteed to give the
# correct quotient when the dividend is less than the squared divisor, and N itself is less than this. This form of division
# can be recognized by its lazy rather than greedy matching of the quotient, and only one divisibility test following that.
(?=(x\1)+(x?(x*))) # \3 = \1+1 = floor(sqrt(N))+1, the number base to work in; \4 = N % \3; \5 = \4-1, or 0 if \4==0
(?=
\4
(x(x*?)) # \6 = floor(N / \3); \7 = \6-1
\1+$
)
(?=
.*
(?=
(?=\4*$) # tail = \4 * \4
\4\5+$
)
(x*?)(?=\3*$) # \8 = (\4 * \4) % \3, the base-\3 digit in place 0 of the result for N*N
(x?(x*?)) # \9 = floor((\4 * \4) / \3); \10 = \9-1, or 0 if \9==0
(
\1+$
|
$\9 # must make a special case for \9==0, because \1 is nonzero
)
)
(?=
.*
(?=
(?=\4*$) # tail = \4 * \6; must do symmetric multiplication, because \4 is occasionally 1 larger than \6
(?=\6*$)
(?=\4\7+$)
\6\5+$
|
$\4 # must make a special case for \4==0, because \6 might not be 0
)
(x*?)(?=\3*$) # \12 = (\4 * \6) % \3
(x?(x*?)) # \13 = floor((\4 * \6) / \3); \14 = \13-1, or 0 if \13==0
(
\1+$
|
$\13 # must make a special case for \13==0, because \1 is nonzero
)
)
(?=
.*(?=\12\12\9$) # tail = 2 * \12 + \9
(x*?)(?=\3*$) # \16 = (2 * \12 + \9) % \3, the base-\3 digit in place 1 of the result for N*N
(x?(x*?)) # \17 = floor((2 * \12 + \9) / \3); \18 = \17-1, or 0 if \17==0
(
\1+$
|
$\17 # must make a special case for \17==0, because \1 is nonzero
)
) # {\6*\6 + 2*\13 + \17} = the base-\3 digit in place 2 of the result for N*N, which is allowed to exceed \3 and will always do so;
# Note that it will be equal to N iff N is a perfect square, because of the choice of number base.
# Step 2: Find the largest M such that 2*M*M is not greater than N*N
# Step 2a: Calculate M*M in base \3
(?=
.*? # Determine value of M with backtracking, starting with largest values first
(?=
( # \20 = M
(?=\3*(x?(x*)))\21 # \21 = M % \3; \22 = \21-1, or 0 if \21==0
(x(x*?)) # \23 = floor(M / \3); \24 = \23-1
\1+$
)
)
(?<=
(?=
(?=
.*
(?=\23*$)
(\23\24+$) # \25 = \23 * \23
)
(?=
.*
(?=
(?=\21*$) # tail = \21 * \21
\21\22+$
)
(x*?)(?=\3*$) # \26 = (\21 * \21) % \3, the base-\3 digit in place 0 of the result for M*M
(x?(x*?)) # \27 = floor((\21 * \21) / \3); \28 = \27-1, or 0 if \27==0
(
\1+$
|
$\27 # must make a special case for \27==0, because \1 is nonzero
)
)
(?=
.*
(?=
(?=\21*$) # tail = \21 * \23; must do symmetric multiplication, because \21 is occasionally 1 larger than \23
(?=\23*$)
(?=\21\24+$)
\23\22+$
|
$\21 # must make a special case for \21==0, because \23 might not be 0
)
(x*?)(?=\3*$) # \30 = (\21 * \23) % \3
(x?(x*?)) # \31 = floor((\21 * \23) / \3); \32 = \31-1, or 0 if \31==0
(
\1+$
|
$\31 # must make a special case for \31==0, because \1 is nonzero
)
)
(?=
.*(?=\30\30\27$) # tail = 2 * \30 + \27
(x*?)(?=\3*$) # \34 = (2 * \30 + \27) % \3, the base-\3 digit in place 1 of the result for M*M
(x?(x*?)) # \35 = floor((2 * \30 + \27) / \3); \36 = \35-1, or 0 if \35==0
(
\1+$
|
$\35 # must make a special case for \35==0, because \1 is nonzero
)
) # {\25 + 2*\31 + \35} = the base-\3 digit in place 2 of the result for M*M, which is allowed to exceed \3 and will always do so
# Step 2b: Calculate 2*M*M in base \3
(?=
.*
(?=\26\26) # tail = 2*\26
(?=\3*(x*)) # \38 = (2*\26) % \3, the base-\3 digit in place 0 of the result for 2*M*M
(\1(x)|) # \40 = floor((2*\26) / \3) == +1 carry if {2*\26} does not fit in a base \3 digit
)
(?=
.*
(?=\34\34\40) # tail = 2*\34 + \40
(?=\3*(x*)) # \41 = (2*\34 + \40) % \3, the base-\3 digit in place 1 of the result for 2*M*M
(\1(x)|) # \43 = floor((2*\34 + \40) / \3) == +1 carry if {2*\34 + \40} does not fit in a base \3 digit
) # 2*(\25 + 2*\31 + \35) + \43 = the base-\3 digit in place 2 of the result for 2*M*M, which is allowed to exceed \3 and will always do so
# Step 2c: Require that 2*M*M <= N*N
(?=
(?=
(.*) # \44
\13\13\17
(?=\6*$) # tail = \6 * \6
\6\7+$
)
\44 # tail = {\6*\6 + 2*\13 + \17}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
(
x+
|
(?=
.*(?!\16)\41 # \41 < \16
|
(?!.*(?!\38)\8) # \38 <= \8
.*(?=\16$)\41$ # \41 == \16
)
)
(\25\31\31\35){2}\43$ # 2*(\25 + 2*\31 + \35) + \43
)
)
^.*
)
)
\20
|xx?\B| # handle inputs in the domain ^x{0,4}$